Linear feedback shift registers (LFSR) are known in the art, and generally come in two type: Fibonacci, and Galois. A typical Galois LFSR (G-LFSR) is shown in FIG. 1. Data is fed in at the right hand side, and taken out of the left. The output bit is fed back into the shift register and XOR'd into certain bits within the shift register at the tap positions, described by a polynomial formed for the shift register. The polynomial for the G-LFSR shown in FIG. 1 is:h(x)=x4+x3+1
This shows that there are taps from the output into the x3 and x0 (i.e. 1) positions of the LFSR. The x4 in the polynomial corresponds to the bit which is shifted out of the shift register.
LFSRs have a number of uses, principally in generating maximal length sequences, and checksums. A sequence is the output obtained from the left hand end of the register when the register is started at some value and zeroes are repeatedly fed into the right hand end; a checksum is the result output from the register (or the register state) once an input data sequence to be checked has been fed through the LFSR. A maximal length sequence occurs when, starting from any non-zero value, the register cycles through all possible non-zero values and returns to the starting value. Such a sequence therefore has length 2n−1, where n is the number of bits in the register.
Practical applications of LFSRs are in generating scrambling codes, for example for use in DS-SS systems such as CDMA-type telecommunications systems (where the scrambling code is generated at a higher rate than the data rate), or for use in “randomisation” of a bitstream, for example to remove long runs of 0's or 1's that may prevent symbol tracking and demodulation.
When used for scrambling code generation, it may be that it becomes necessary to advance the LFSR by several steps, for example to jump from one scrambling code in the sequence to another scrambling code that may be several (hundred or thousand) positions away. In this case, conventionally it is necessary to run the shift register the number of input cycles that the shift register is desired to advance. This takes time and power, thus meaning that it has not heretofore been possible for a LFSR to jump directly to a particular state required.